//
// Created by cheng on 2021/02/21.
//

#include <iostream>
#include <vector>

using namespace std;

long cnt = 0;

// 合并两个已排序数组
void Merge(vector<int>& a, int left, int mid, int right);
// 归并排序
void MergeSort(vector<int>& arr, int left, int right);

int main() {
    vector<int> arr = {8, 5, 9, 2, 6, 3, 7, 1, 10, 4};
    for (auto i : arr) {
        cout << i << " ";
    }
    cout << endl;
    MergeSort(arr, 0, 10);
    for (auto i : arr) {
        cout << i << " ";
    }
    cout << endl;
}

void Merge(vector<int>& a, int left, int mid, int right) {
    for (auto i : a) {
        cout << i << " ";
    }
    cout << endl;
    int len1 = mid - left, len2 = right - mid;
    auto arr1 = new int[len1];
    auto arr2 = new int[len2];

    for (int i = 0; i < len1; i++) {
        arr1[i] = a[left+i];
    }
    for (int i = 0; i < len2; i++) {
        arr2[i] = a[mid+i];
    }
    for (int k = left, i = 0, j = 0; k < right; k++) {
        cnt++;
        if (arr1[i] <= arr2[j]) {
            a[k] = arr1[i++];
        } else {
            a[k] = arr2[j++];
        }
    }
    delete[] arr1;
    delete[] arr2;
}

void MergeSort(vector<int>& arr, int left, int right) {
    if (left+1 < right) {
        int mid = (left+right) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid, right);
        Merge(arr, left, mid, right);
    }
}
